import sun.reflect.generics.tree.Tree;

import javax.xml.bind.annotation.XmlInlineBinaryData;
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
class KthLargest {
    int val=0;
    public boolean isUnivalTree(TreeNode root) {
        this.val=root.val;
        return dfs(root);
    }
    public boolean dfs(TreeNode root){
        if(root==null){
            return true;
        }
        if(root.val!=this.val){
            return false;
        }
        return dfs(root.left)&&dfs(root.right);
    }







    public Queue<Integer> queue=new PriorityQueue<>();
    public int k=0;
    public KthLargest(int k, int[] nums) {
        this.k=k;
        for(int n : nums){
            add(n);
        }
    }

    public int add(int val) {
        queue.offer(val);
        if(queue.size()>k){
            queue.poll();
        }
        return queue.peek();
    }
}





public class Solution {
    int count=0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(root,0);
        return count;
    }
    public void dfs(TreeNode root,int a){
        if(root!=null){
            a=a*2+root.val;
            if(root.right==null&&root.left==null){
                count+=a;
                return ;
            }
            dfs(root.left,a);
            dfs(root.right,a);
        }
    }





    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0){
            return null;
        }
        return dfs(nums,0,nums.length-1);
    }
    public TreeNode dfs(int[] nums,int start,int end){
        if(start>end){
            return null;
        }
        int mid=(start+end)/2;
        TreeNode root= new TreeNode(nums[mid]);
        root.left=dfs(nums,start,mid-1);
        root.right=dfs(nums,mid+1,end);
        return root;
    }






    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> arr=new ArrayList<>();
                while(size>0){
                    TreeNode tmp=queue.poll();
                    arr.add(tmp.val);
                    if(tmp.left!=null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.offer(tmp.right);
                    }
                    size--;
                }
                list.add(arr);
            }
        }
        return list;
    }








    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((root.val-p.val)*(root.val-q.val)<=0){
            return root;
        }
        return p.val<root.val?lowestCommonAncestor(root.left,p,q):lowestCommonAncestor(root.right,p,q);

    }








    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) {
            return root;
        }
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null){
            return right;
        }
        if(right==null){
            return left;
        }
        return root;
    }






    TreeNode head=new TreeNode(-1);
    TreeNode curs=head;
    public TreeNode increasingBST(TreeNode root) {
        if(root.left!=null ){
            increasingBST(root.left);
        }
        curs.right=new TreeNode(root.val);
        curs=curs.right;
        if(root.right!=null){
            increasingBST(root.right);
        }
        return head.right;
    }






    TreeNode prev=null;
    public void Converts(TreeNode pcur) {
        if(pcur==null){
            return ;
        }
        Converts(pcur.left);
        pcur.left=prev;
        if(prev==null){
            prev=pcur;
        }else{
            prev.right=pcur;
            prev=pcur;
        }
        Converts(pcur.right);
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        Converts(pRootOfTree);
        while(pRootOfTree.left!=null){
            pRootOfTree=pRootOfTree.left;
        }
        return pRootOfTree;
    }










    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> arr=new ArrayList<>();
                while(size>0){
                    TreeNode tmp=queue.poll();
                    arr.add(tmp.val);
                    if(tmp.left!=null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.offer(tmp.right);
                    }
                    size--;
                }
                list.add(arr);
            }
        }
        return list;
    }





//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root==null||root==p||root==q){
//            return root;
//        }
//        TreeNode left=lowestCommonAncestor(root.left,p,q);
//        TreeNode right=lowestCommonAncestor(root.right,p,q);
//        if(left==null){
//            return right;
//        }
//        if(right==null) {
//            return left;
//        }
//        return root;
//    }
}